package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/">二叉树的层序遍历 II( Binary Tree Level Order Traversal II)</a>
 * <p>给你二叉树的根节点root，返回其节点值<b>自底向上的层序遍历</b>。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）</p>
 * <pre>
 * 示例 1：
 *      输入：root = [3,9,20,null,null,15,7]
 *              3
 *             / \
 *            9  20
 *               / \
 *              15  7
 *      输出：[[15,7],[9,20],[3]]
 *
 * 示例 2：
 *      输入：root = [1]
 *      输出：[[1]]
 *
 * 示例 3：
 *      输入：root = []
 *      输出：[]
 * </pre>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数目在范围 [0, 2000] 内</li>
 *     <li>-1000 <= Node.val <= 1000</li>
 * </ul>
 *
 * @author c2b
 * @see LC0102BinaryTreeLevelOrderTraversal_M 二叉树的层序遍历
 * @see LC0107LevelOrderBottom_M 二叉树的层序遍历II(自底向上输出每一层)
 * @since 2023/5/11 11:48
 */
public class LC0107LevelOrderBottom_M {
    static class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> resultList = new ArrayList<>();
            if (root == null) {
                return resultList;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int currLevelNodeSize = queue.size();
                List<Integer> currLevelNodeValList = new ArrayList<>();
                for (int i = 0; i < currLevelNodeSize; i++) {
                    TreeNode currNode = queue.poll();
                    currLevelNodeValList.add(currNode.val);
                    if (currNode.left != null) {
                        queue.offer(currNode.left);
                    }
                    if (currNode.right != null) {
                        queue.offer(currNode.right);
                    }
                }
                resultList.add(0, currLevelNodeValList);
            }
            return resultList;
        }
    }
}
